#!/usr/bin/env python

def find(record, node):
    if record[node] != node:
        record[node] = find(record, record[node])
    
    return record[node]

def union(record, edge):
    u, v = find(record, edge[0]), find(record, edge[1])
    record[u] = v

def node_cmp(v1, v2):
    return (v1, v2) if v1 < v2 else (v2, v1)

def kruskal(graph, init_node):
    edge_dict = {}
    for node in graph.keys():
        edge_dict.update({node_cmp(node, k) : v for k, v in graph[node].items()})
    
    sorted_edge = list(sorted(edge_dict.items(), key = lambda kv : kv[1]))

    tree = []
    connected_records = {key : key for key in graph.keys()}
    
    for edges, _ in sorted_edge:
        if find(connected_records, edges[0]) != \
           find(connected_records, edges[1]):
           tree.append(edges)
           union(connected_records, edges)
    return tree

if __name__ == '__main__':
    graph_dict = {
        "A": {"B": 7, "D": 5},
        "B": {"A": 7, "C": 8, "D": 9, "E": 5},
        "C": {"B": 8, "E": 5},
        "D": {"A": 5, "B": 9, "E": 15, "F": 6},
        "E": {"B": 7, "C": 5, "D": 15, "F": 8, "G": 9},
        "F": {"D": 6, "E": 8, "G": 11},
        "G": {"E": 9, "F": 11}
    }

    path = kruskal(graph_dict, "D")
    print(path)  # [('A', 'D'), ('D', 'F'), ('A', 'B'), ('B', 'E'), ('C', 'E'), ('E', 'G')]